2D Strip Packing Problem (SPP)

This web page was designed to give background information to a paper by Nthabiseng Ntene and Jan van Vuuren entitled A survey and comparison of level heuristics for the 2D oriented strip packing problem in which some classical heuristics from the literature as well as some suggested modifications are presented. A new heuristic is also proposed.

Packing problems have been proven to be NP-hard and as such many researchers have concentrated on finding approximation algorithms. The class of algorithms studied for solving the 2D strip packing problem is called level algorithms which are primarily used when the entire information about the items to be packed is available. In this class, the strip is divided into horizontal levels whose height corresponds to the height of the tallest rectangle packed on a previous level. The first level is the bottom of the strip.

The performance of heuristics were tested on a wide range of benchmark data sets. The benchmark data sets presented on this page is a collection of data from different sources. The idea behind developing this page is to allow other researchers to use the benchmark data and avoid having to generate new data sets to test algorithms. This will also allow proper comparisons between algorithms when using the same benchmark data sets.

1. Next-Fit Decreasing Height (NFDH). Items are pre-ordered according to non-increasing height. Items are packed on a level and if an item does not fit on the current level, a new level is created on top of the top level. Previously packed levels are never revisited.
2. First-Fit Decreasing Height (FFDH). Items are first sorted according to non-increasing height. Items are packed on the lowest level where it fits. A new level is created on top of the top level if an item does not fit in any of the existing levels.
3. Best-Fit Decreasing Height (BFDH). Items are pre-ordered according to non-increasing height. Items are packed on a level with minimum residual horizontal space.
4. Split Fit (SF). Items are divided into two sublists of narrow and wide. The wide rectangles are packed first using the FFDH algorithm. The packed items are then rearranged such that the widest are at the bottom. This rearrangement leaves a rectangular region that will be used to insert the narrow items using the FFDH algorithm. If none of the narrow items fit into this region then packing continues above the wide items.
5. Floor-Ceiling No Rotation (FCNR). Within a level, a floor is defined as the horizontal line coinciding with the bottom edges of items packed on that level and a ceiling is a horizontal line coinciding with the upper edge of the tallest item packed on that level. Items are preferrably packed on the ceiling and if there is insufficient ceiling space then floor packing is considered. If an item does not fit either on the ceiling or floor then a new level is created above the top level and the item will initialise the level by being packed on the floor.
6. Knapsack01 (KP01). Items are first sorted according to non-increasing height. A level is initialised by packing an item of greatest height, then a knapsack problem is solved amongst the unpacked items.

1. Next-Fit Decreasing Height Decreasing Width (NFDHDW). Items of equal height are resolved by non-increasing width
2. Next-Fit Decreasing Height Increasing Width (NFDHIW). Items of equal height are resolved by non-decreasing width.
3. First-Fit Decreasing Height Decreasing Width (FFDHDW). Pre-ordering of items of equal height is additionally resolved by non-increasing width.
4. First-Fit Decreasing Height Increasing Width (FFDHIW). Pre-ordering of items of equal height is additionally resolved by non-decreasing width.
5. Best-Fit Decreasing Height Decreasing Width (BFDHDW). Items of equal height are additionally resolved by non-increasing width.
6. Best-Fit Decreasing Height Increasing Width (BFDHIW). Items of equal height are additionally resolved by non-decreasing width.
7. Size Alternating Stack (SAS) . Items are split into two sublists of narrow and wide. The height of a level is determined by the tallest rectangle between the two sublists. From the left to the right of the strip we alternate between the two sublists and rectangles in the same sublist are then stacked from top to bottom.

1. Wang and Valenzuela benchmark data (2001). Two classes of data sets called nice and path were generated. The former consists of rectangles of similar sizes and shapes while the latter consists of rectangles with significantly varying shapes and sizes. Data sets of sizes n = 25, 50, 100, 200, 500 were generated each with 50 tests instances except for the case n = 500 where only ten test instances were generated. The test instances are denoted by nice.n and path.n and a total of 420 data sets were generated.
2. Hopper and Turton benchmark data (2001). Twenty one data sets (denoted C _i^j) ranging from 17 to 197 rectangles were generated. The subscript i represents seven categories while the superscript j represents three test instances. The data sets were randomly generated maintaining an aspect ratio of 7 with known optimal solutions of all test instances.
3. Hopper and Turton benchmark data (2002). Guillotineable (denoted T _i^j) and non-guillotineable data sets (denoted H _i^j) were generated from a 200 x 200 square.
4. Burke benchmark data (2004). Twelve data sets (denoted B_i) were generated through slicing a large rectangle repeatedly either vertically or horizontally to such that two rectangles are generated after each cut. Before each slicing, it is ensured that the dimensions generated are not smaller than the minimum dimension specified and the process is carried out until the required number of rectangles is obtained.
5. Christofides and Whitlock benchmark data (1977). Data sets for cutting stock problem and these were transformed and adapted for strip packing problems (denoted G_i (i = 1,2,3)) were generated. The data were generated by sampling from a uniform distribution in the range [0, 0.25A], where A is the area of the inital large rectangle.
6. Beasley benchmark data. Beasley (1985a) generated data sets (denoted U₁,U₂,U₃,U₄) for the unconstrained guillotine cutting problem. The heights were sampled from uniform distributions [H/4, 3H/4] while the widths were sampled from [w/4, 3w/4]. Twelve non-guillotineable random problem instances (denoted V₁,...,V₁₂) were generated by Beasley (1985b). These were also transformed and adapted to strip packing problems.

References

Home